package ds

type SinglyLinkedQueue[T comparable] struct {
	size int
	head, tail *SinglyLinkedNode[T]
}

func InitializeSinglyLinkedQueue[T comparable]() *SinglyLinkedQueue[T] {
	head := &SinglyLinkedNode[T]{}
	return &SinglyLinkedQueue[T]{
		head: head,
		tail: head,
	}
}

func (q *SinglyLinkedQueue[T]) Empty() bool {
	return q.size == 0
}

func (q *SinglyLinkedQueue[T]) Size() int {
	return q.size
}

func (q *SinglyLinkedQueue[T]) Enqueue(x T) {
	node := &SinglyLinkedNode[T]{Val: x}
	q.tail.Next = node
	q.tail = q.tail.Next
	q.size++
}

func (q *SinglyLinkedQueue[T]) Dequeue() (*SinglyLinkedNode[T], bool) {
	if q.Empty() {
		return nil, false
	}

	node := q.head.Next
	q.head.Next = node.Next

	q.size--
	return node, true
}

type DoublyLinkedQueue[T comparable] struct {
	size int
	head, tail *DoublyLinkedNode[T]
}

func InitializeDoublyLinkedQueue[T comparable]() *DoublyLinkedQueue[T] {
	head := &DoublyLinkedNode[T]{}
	tail := &DoublyLinkedNode[T]{}
	head.Next = tail
	tail.Previous = head
	return &DoublyLinkedQueue[T]{
		head: head,
		tail: tail,
	}
}

func (q *DoublyLinkedQueue[T]) Empty() bool {
	return q.size == 0
}

func (q *DoublyLinkedQueue[T]) Size() int {
	return q.size
}

func (q *DoublyLinkedQueue[T]) Enqueue(x T) {
	node := &DoublyLinkedNode[T]{
		Val: x,
		Previous: q.tail.Previous,
		Next: q.tail,
	}
	node.Previous.Next = node
	node.Next.Previous = node
	q.size++
}

func (q *DoublyLinkedQueue[T]) Dequeue() (*DoublyLinkedNode[T], bool) {
	if q.size == 0 {
		return nil, false
	}

	node := q.head.Next
	q.head.Next = node.Next
	q.head.Next.Previous = q.head
	q.size--
	return node, true
}
